#include<stdio.h>
#include<stdlib.h>
#include<strings.h>


/*
 *  这是计数排序的示例
 *  作者：Tmacy
 *  时间：2013-11-27
 *
 */

void counting_sort(int *a,const int size_a,int *b,int k);

int max(int *a,const int size_a); 

int main(int argc, const char *argv[])
{
    int a[10] = {20,8,11,2,12,6,5,0,4,7};
    int b[10] = {0};

    int size_a = sizeof(a) / sizeof(int);

    int k = max(a,size_a);

    counting_sort(a,size_a,b,k);


    for(int i = 0;i < size_a;i++){
        printf("%d ",a[i]);
    }
    putchar(10);
    
    for(int i = 0;i < size_a;i++){
        printf("%d ",b[i]);
    }
    putchar(10);

    return 0;
}


/*
 * 求数组a的最大值
 * 返回值为数组a的最大值
 *
 */
int max(int *a,int size_a){

    int m = 0;
    int i;

    for(i = 0,m = i;i < size_a;i++){
        if(a[m] < a[i]){
            m = i;
        }
        printf("a[%d]:%d\n",m,a[m]);
    }
    
    printf("a[%d]:%d\n",m,a[m]);


    return a[m];
}

/*
 * 计数排序 数组a是需要排序的数组，结果放在数组b中
 * k表示数组中最大值
 *
 */
void counting_sort(int *a,const int size_a,int *b,int k){
    int* c = (int*)malloc(sizeof(int) * (k + 1));

    bzero(c,(k + 1)*sizeof(int));

    for(int j = 0;j < size_a;j++){   //c[i]中包含了等于i的元素个数
        c[a[j]]++;
    }

    for(int i = 1;i < k + 1;i++){
        c[i] = c[i] + c[i - 1];      //c[i]中包含了小于或等于i的元素个数
    }

    for(int i = 0;i < k + 1;i++){
        printf(" %d : %d\n",i,c[i]);
    }
    
    for(int j = size_a - 1;j >= 0;j--){
        b[c[a[j]] - 1] = a[j];
        c[a[j]]--;
    }
    
    free(c);
    c = NULL;
    
    return ;
}



